package com.ln.leetcode._1262;

import org.junit.Test;

import java.util.Arrays;

/**
 * 1262. 可被三整除的最大和
 * <p>
 * 给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [3,6,5,1,8]
 * 输出：18
 * 解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。
 * 示例 2：
 * <p>
 * 输入：nums = [4]
 * 输出：0
 * 解释：4 不能被 3 整除，所以无法选出数字，返回 0。
 * 示例 3：
 * <p>
 * 输入：nums = [1,2,3,4,4]
 * 输出：12
 * 解释：选出数字 1, 3, 4 以及 4，它们的和是 12（可被 3 整除的最大和）。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 4 * 10^4
 * 1 <= nums[i] <= 10^4
 * <p>
 */
public class Solution {

    @Test
    public void test() {
//        System.out.println(maxSumDivThree(new int[]{3,6,5,1,8}));
        System.out.println(maxSumDivThree(new int[]{4,4}));
    }

    public int maxSumDivThree(int[] nums) {
        // 定义一个数组，分别标识  %3=0、%3=1、%3=2 的情况
        // 题目需要求被3整除的数字之和，所以第一个为初始值0，后面两个表示不能被3整除的情况，表示负无穷
        int[] sum = {0, Integer.MIN_VALUE, Integer.MIN_VALUE};
        // 遍历数组
        for (int num : nums) {
            // tmp
            int[] tmp = new int[3];
            System.arraycopy(sum, 0, tmp, 0, 3);
            for (int index = 0; index < 3; index++) {
                // 用
                int modIndex = (index + num) % 3;
                tmp[modIndex] = Math.max(tmp[modIndex], sum[index] + num);
            }
            sum = tmp;
        }

        Arrays.stream(sum).forEach(System.out::println);

        return sum[0];
    }

}
